package leetcode每日一题;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 *
 * 2. 算法分析
 *      分析：(先将数组按照升序排列)
 *         如果数组中没有负数，则最大值一定是数组的最后三个元素的乘积
 *         如果数组存在负数，则情况有可能就发生改变了：
 *            如果只有一个负数，则还是最后三个元素的乘积
 *            如果负数的个数大于等于2，则需要分情况讨论
 *               1. 绝对值最大的两个负数 * 最大的正数
 *               2. 最大的三个正数
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 乘积最大的三位数 {
    public static void main(String[] args) {

    }

    /**
     * 排序法  时间复杂度完全依赖于排序的复杂度，调用的底层的sort方法，所以总的时间复杂度为O(nlogn)
     * 效率比较低
     * @param nums
     * @return
     */
    public static int maximumProduct1(int[] nums) {
        Arrays.sort(nums); // 按照升序排列
        int negetives = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] >= 0) {
                break;
            }
            negetives++;
        }
        int len = nums.length;
        if(negetives <= 1) {
            return nums[len - 1] * nums[len - 2] * nums[len - 3];
        }
        return Math.max(nums[0] * nums[1] * nums[len - 1],nums[len - 1] * nums[len - 2] * nums[len - 3]);
    }


}
